﻿using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace CodeTop.CodeTop
{
    public class Solution93
    {
        IList<string> res = new List<string>();
        public IList<string> RestoreIpAddresses(string s)
        {
            IList<string> path = new List<string>();
            DFS(s, 0, 0, path);
            return res;

        }

        private void DFS(string s, int start, int depth, IList<string> path)
        {

            if (depth == 3)
            {
                //收集

                if (start < s.Length)
                {
                  
                    if (IsVaild(s, start, s.Length - 1))
                    {
                        string str = s.Substring(start, s.Length - start);
                        path.Add(str);
                        string cur = "";
                        for (int i = 0; i < path.Count - 1; i++)
                        {
                            cur += path[i];
                            cur += '.';


                        }
                        cur += path[path.Count - 1];
                        res.Add(cur);
                    }
                }


                return;

            }

            for (int i = start; i < s.Length; i++)
            {
                //当前子串




                //检测子串合法
                if (IsVaild(s, start, i))
                {
                    string str = s.Substring(start, i - start + 1);
                    path.Add(str);
                    DFS(s, i + 1, depth + 1, new List<string>(path));

                    path.RemoveAt(path.Count - 1);
                }
                else
                {
                    break;
                }



            }
        }

        private bool IsVaild(string s, int start, int end)
        {

            int len = end - start + 1;
            if (len > 3)
            {
                return false;
            }
            if (s[start] == '0' && start != end)
            {
                // 0开头的数字不合法,除非只有一个0
                return false;
            }

            string str = s.Substring(start, len);



            int num = int.Parse(str);

            if (num < 0 || num > 255)
            {
                return false;
            }



            return true;

        }
    }

    class Program93
    {


        static void Main93(string[] args)
        {

            string s = "101023";

            Solution93 solution = new Solution93();
            IList<string> res = solution.RestoreIpAddresses(s);
            for (int i = 0; i < res.Count; i++)
            {
                Console.WriteLine(res[i]);
            }

        }
    }




}
